package middle;

public class Solution_400 {

    public static void main(String[] args) {
        Solution_400 model = new Solution_400();
        System.out.println(model.findNthDigit(1)); // 1
        System.out.println(model.findNthDigit(3)); // 3
        System.out.println(model.findNthDigit(11)); // 0
        System.out.println(model.findNthDigit(31)); // 0
        System.out.println(model.findNthDigit(99)); // 4
        System.out.println(model.findNthDigit(123)); // 6
        System.out.println(model.findNthDigit(Integer.MAX_VALUE)); // 2
        System.out.println(model.findNthDigit(1111)); // 4
//        System.out.println(Integer.MAX_VALUE);
    }
    public int findNthDigit(int n) {
        int pre = 0, step = 9, pre_count = 0, count = 1;
        long next_count = pre_count + step * count;
        while (n > next_count) {
            pre_count += step * count;
            pre += step;
            step *= 10;
            count++;
            next_count = pre_count + (long) step * count;
        }
        int sub = n - pre_count;
        pre += ((sub + count - 1) / count);
        int mod = sub % count;
        mod = count - (mod == 0 ? count : mod) + 1;

        while (mod-- > 1) {
            pre /= 10;
        }
        return pre % 10;
    }
}
